package Work;
/**
 * 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
 * 给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
 */
import java.util.*;
 class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Test1 {
    public boolean chkPalindrome(ListNode A) {
       ListNode fast=A;
       ListNode slow=A;
       /*1:先找中间结点
       2:将中间节点以后翻转过来*/
        while (fast !=null && fast.next!=null){
            //用快慢指针，fast走2步，slow走1步
            fast=fast.next.next;
            slow=slow.next;
        }//slow就是中间结点
        //翻转
        ListNode listNode=slow.next;
        while ( listNode !=null){
            //用头插法反转链表
            ListNode listNode1 = listNode.next;
            listNode.next=slow;
            slow=listNode;
            listNode=listNode1;
        }
        while (slow != A){
            if (slow.val != A.val){
                return  false;
            }
            if (A.next == slow){
                //判断偶数情况
                return true;
            }
            slow=slow.next;
            A=A.next;
        }
        return  true;

    }
    public static void main(String[] args) {

    }


}
